/******************************************************************************
                         COPYRIGHT 1955-2008 by BUPT ISC.
                        北京邮电大学信息安全中心 版权所有
                           Web: http://www.bupt.edu.cn
 *******************************************************************************/
/*******************************************************************************
  文件名： hash.h
  项目：   
  模块：   common
  作者：   huangwei
  版本：   0.2
  创建于:  2008-11-04 
  描述：
    Hash表数据结构声明和基本操作方法声明

  修改历史：
  日期：     修改人：    修改描述：
  09/05/14   huangwei    1.修改removeHash和removeBucketInHash的函数返回值为void
                         2.修正了部分函数的注释
 *********************************************************************************/
#include <malloc.h>

#ifndef _HASH_TABLE_H
#define _HASH_TABLE_H

/******************************************************************************
  函数名：Hash节点元素比较回调函数
  功能描述：
    1.用于Hash碰撞检测
    2.比较两个Hash节点元素Key是否相同    

  输入参数：
    void * Hash节点元素1
    void * Hash节点元素2

  输出参数：
    无

  返回值：
    0   表示两个Hash节点Key相同
    非0 表示两个Hash节点Key不相同
       （但映射到了同一个index，在addToHash中就表示出现了Hash碰撞）


 *****************************************************************************/
typedef int (*HASH_COMP_CB)(void *, void *);


/******************************************************************************
  函数名：Hash算法回调函数
  功能描述：
    将输入数据应用散列算法分散到Hash表中
    对于相同"键值"的Hash节点，在同一个Hash表中应用此算法应该返回相同的入口点值

  输入参数：
    void * Hash节点元素
    int    Hash表容量大小

  输出参数：
    无

  返回值：
    Hash散列表的入口索引值  
 *****************************************************************************/
typedef int (*HASH_CHOOSE_CB)(void *, int);

/******************************************************************************
  函数名：Hash节点元素内存释放回调函数
  功能描述：
    释放Hash节点元素中存储的数据结构从堆中动态分配得到的内存
    如果Hash节点元素中存储的数据结构未使用堆内存分配，则可将该函数指针置为NULL

  输入参数：
    void * 待释放内存的Hash节点元素地址指针

  输出参数：
    无

  返回值：
    无
 *****************************************************************************/
typedef void (*HASH_FREE_CB)(void *);

typedef struct _HASH_NODE_T
{
    void   *pData;                /* 存储在节点中的数据 */
    struct _HASH_NODE_T *pstNext; /* 链表中下一个节点地址 */
}HASH_NODE_T;

typedef struct _HASH_ITERATOR
{
    int    iIndex;                     /* 迭代器在链表中的当前位置 */
    struct _HASH_NODE_T *pstBucket;      /* 当前节点地址 */
    struct _HASH_NODE_T *pstPrevBucket;  /* 前一个节点地址 */
    struct _HASH_NODE_T **pstFirstBucket;/* 头节点地址 */
}HASH_IT_T;

typedef struct _HASH_TABLE_T
{
    struct         _HASH_NODE_T **pstTable;/* Hash链表中用于存储元素的节点地址表 */
    int            iElements;              /* Hash表中实际元素的个数*/
    int            iSize;                  /* Hash表的容量 */
    HASH_COMP_CB   pifnCompare;            /* Hash值比较回调函数指针 */
    HASH_CHOOSE_CB pifnChoose;             /* Hash链表入口位置查找回调函数指针 */
    HASH_FREE_CB   pfnFree;                /* Hash节点中数据的内存释放回调函数指针 */
}HASH_TABLE_T;


#ifdef ADD_HASH_OK
#undef ADD_HASH_OK
#endif

#ifdef COLLISION_FOUND
#undef COLLISION_FOUND
#endif

#ifdef MALLOC_FAILED
#undef MALLOC_FAILED
#endif

#ifdef HASH_KEY_MATCH
#undef HASH_KEY_MATCH
#endif

#define HASH_KEY_MATCH 0   /* Hash键值相等 */
#define ADD_HASH_OK 0      /* addToHash成功时的返回值 */
#define COLLISION_FOUND -1 /* addToHash失败，失败原因是因为键值冲突 */
#define MALLOC_FAILED -2   /* malloc内存失败 */

#define ENABLE_FREE_DATA_CB 1
#define DISABLE_FREE_DATA_CB 0

/* 初始化Hash链表为空Hash表 */
void initHash(HASH_TABLE_T *pstHash);

/* 释放Hash链表中所有节点所占用的内存 */
void deleteHash(HASH_TABLE_T *pstHash, int iEnableFreeCb);

/* 遍历Hash表，并返回Hash迭代器 */
HASH_IT_T *iterateHash(HASH_TABLE_T *pstHash,HASH_IT_T *pstHashIt);

/* 创建Hash表 */
HASH_TABLE_T *newHashTable(int iSize, HASH_COMP_CB pfnHashCmpCb, HASH_CHOOSE_CB pfnHashChooseCb, HASH_FREE_CB pfnHashFreeCb);

/* 将数据加入到Hash表中 */
int addToHash(HASH_TABLE_T *pstHash, void *pData);

/* 在Hash表中根据数据内容查找数据 */
HASH_NODE_T *findInHash(HASH_TABLE_T *pstHash, void *pData);

/* 在Hash表中删除一个节点 */
void removeBucketInHash(HASH_TABLE_T *pstHash, HASH_IT_T *pstHashIt);

/* 在Hash表中根据数据内容删除一个节点 */
void removeHash(HASH_TABLE_T *pstHash, void *pData);

/* 调整Hash表的容量 */
HASH_TABLE_T *resizeHash(HASH_TABLE_T *pstHash, int iSize);

/* 调试并打印Hash表中的内容 */
void debugHash(HASH_TABLE_T *pstHash);

#endif
